import numpy as np
import matplotlib.pyplot as plt
import sys

'''
    Dense Block Detection
    M1. A near-linear greedy algorithm
'''

def get_max_id(data_path):
    # 数据集中的用户和商家id都是从1开始的
    max_user_id = 0
    max_item_id = 0
    with open(data_path, "r") as file:
        lines = file.readlines()
        for line in lines:
            line = line.split("\t")
            if int(line[0]) > max_user_id:
                max_user_id = int(line[0])
            if int(line[1]) > max_item_id:
                max_item_id = int(line[1])
    return max_user_id, max_item_id

def load_data(data_path, user_size, item_size):
    # 每一行表示一个用户对各个商家的点赞情况，每一列表示一个商家接收到的所有用户的点赞情况

    adj_matrix = np.zeros([user_size, item_size])
    with open(data_path, "r") as file:
        lines = file.readlines()
        for line in lines:
            line = line.split("\t")
            adj_matrix[int(line[0]) - 1][int(line[1]) - 1] = float(line[2])
    return adj_matrix


def greedy_algorithm(adj_matrix):

    density = []
    count = 0
    #记录最大密度子图的结构
    shape = None
    max_density = 0
    while True:
        # 计算当前总的数学平均度
        avg_deg = adj_matrix.sum() / (adj_matrix.shape[0] + adj_matrix.shape[1])
        density.append(avg_deg)
        if max_density < avg_deg:
            max_density = avg_deg
            shape = adj_matrix.shape

        # 遍历所有的用户和item找出度最小的那一行或者那一列
        min_user_deg = sys.maxsize
        min_user_deg_id = 0
        for i in range(adj_matrix.shape[0]):
            # 遍历每一个用户
            deg = np.sum(adj_matrix[i])
            if deg < min_user_deg:
                min_user_deg = deg
                min_user_deg_id = i
        min_item_deg = sys.maxsize
        min_item_deg_id = 0
        for j in range(adj_matrix.shape[1]):
            # 遍历每一个item
            deg = np.sum(adj_matrix[:,j])
            if deg < min_item_deg:
                min_item_deg = deg
                min_item_deg_id = j
        if min_user_deg < min_item_deg:
            # 删除 max_user_deg_id 行
            adj_matrix = np.delete(adj_matrix, min_user_deg_id, axis=0)
        else:
            # 删除 max_item_deg_id 列
            adj_matrix = np.delete(adj_matrix, min_item_deg_id, axis=1)
        #如果某个维度变成了0：则停止
        if adj_matrix.shape[0] == 0 or adj_matrix.shape[1] == 0:
            break
        count += 1

        if count % 20 == 0:
            print("邻接矩阵当前的维度为: {}".format(adj_matrix.shape))

    return density, shape, max_density
def draw_density_pic(density):
    x = [i for i in range(len(density))]
    plt.plot(x, density, "b", marker='D', markersize=5, label="density")
    plt.xlabel("Iteration")
    plt.ylabel("Density")
    plt.title("Greedy Algorithm")
    plt.savefig("hw3_1.jpg")

if __name__ == "__main__":
    data_path = "./data/out.wang-amazon"
    max_user_id, max_item_id = get_max_id(data_path)
    adj_matrix = load_data(data_path, max_user_id, max_item_id)
    density, shape, max_density = greedy_algorithm(adj_matrix)
    draw_density_pic(density)
    print("最大的密度为:{}，此时的子图大小为:{}".format(max_density, shape))